package com.cat.chapter050;

import java.util.Arrays;

/**
 * @author cat
 * @description https://leetcode.cn/problems/trapping-rain-water/description/
 * @create 2025/7/21 09:39
 * @since JDK17
 */

public class Solution01 {
    static int MAXN = 20010;
    static int[] lmax = new int[MAXN];
    static int[] rmax = new int[MAXN];
    public int trap(int[] height) {
        int n = height.length, ans = 0;
        Arrays.fill(lmax, 0, n, 0);
        Arrays.fill(rmax, 0, n, 0);
        lmax[0] = height[0];
        rmax[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            lmax[i] = Math.max(lmax[i - 1], height[i]);
        }

        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i + 1], height[i]);
        }

        for (int i = 1; i < n - 1; i++) {
            ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - height[i]);
        }
        return ans;
    }
}
